package algorithm.sort;

import java.util.Arrays;

//希尔排序--交换法和移动法
public class ShellSort {
    public static void main(String[] args) {
        int[] data =   new int[]{5,3,-1,6,9,7,5};
        shellSort2(data);
        System.out.println(Arrays.toString(data));
    }



    //对交换式的希尔排序进行优化->交换法(太费时间)
    public static void shellSort(int[] data){
        for (int step = data.length/2;step>0;step/=2){

            for (int i = step; i <data.length ; i++) {
                for (int j=i-step;j>0;j-=step){
                    if (data[j]>data[j+step]){
                        int temp = data[j];
                        data[j] = data[j+step];
                        data[j+step]=temp;
                    }
                }
            }
        }

    }


    //对交换式的希尔排序进行优化->移位法
    public static void shellSort2(int[] data){
        for (int step = data.length/2;step>0;step/=2){
            for (int i =step;i<data.length;i++){
                    int j = i;
                    int value = data[j];
                    if (data[j]<data[j-step]){
                        while (j-step>=0 && data[j-step]>value){
                            data[j] = data[j-step];
                            j -=step;
                        }
                        data[j]=value;
                    }
            }
        }
    }
}
